package array.medium;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 合并区间
 * 示例 1：
 *
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * 示例 2：
 *
 * 输入：intervals = [[1,4],[4,5]]
 * 输出：[[1,5]]
 * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-intervals
 */
public class MergeIntervals_56 {

    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        LinkedList<int[]> list = new LinkedList<>();
        int l = 0;
        while (l < intervals.length) {

            if (list.isEmpty())
                list.offer(intervals[l++]);
            else if (list.peekLast()[0] <= intervals[l][0] && list.peekLast()[1] >= intervals[l][1])
                l++;
            else if (list.peekLast()[1] < intervals[l][0])
                list.offer(intervals[l++]);
            else
                list.offer(mergeArr(list.pollLast(), intervals[l++]));
        }
        int[][] arr = new int[list.size()][2];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.pollFirst();
        }
        return arr;
    }

    public int[] mergeArr(int[] num1, int[] num2) {
        return new int[]{num1[0], num2[1]};
    }


    public static void main(String[] args) {
        MergeIntervals_56 mi = new MergeIntervals_56();
        //[1, 4][0, 4]
        //{2,3},{2,2},{3,3},{1,3},{5,7},{2,2},{4,6}
        //
        int[][] merge = mi.merge(new int[][]{{1,4},{0,4}});
        for (int[] ints : merge) {
            System.out.println(ints[0] + " " + ints[1]);
        }

    }
}
